package hyy_2022;

import commons.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 二叉树最大深度
 */
public class _0724_104_TreeMaxDepth {


    /**
     * 深度优先搜索 DFS Depth First Search
     * 递归计算出左子树和右子树的最大深度,然后再o(1)时间内计算出当前二叉树的最大深度
     * @param root
     * @return int
     */
    public static int maxHeihtByDFS(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            int leftHeight = maxHeihtByDFS(root.left);
            int rightHeight = maxHeihtByDFS(root.right);
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }

    /**
     * 广度优先算法 BFS Breadth First Search
     * 特点1: 队列存放当前层所有节点
     * 特点2: 需将队列里所有节点都拿出来进行扩展,这样能保证每次扩展完的时候队列里存放的是当前层的所有节点
     * poll(): 返回队列开头的元素
     * offer(e): 插入队列中的元素
     * @param root
     * @return int
     */
    public static int maxHeightByBFS(TreeNode root) {
        if(root == null){
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        //用ans维护拓展的次数
        int ans = 0;
        while(!queue.isEmpty()) {
            int size = queue.size();
            while(size > 0) {
                TreeNode node = queue.poll();
                if(node.left != null) {
                    queue.offer(node.left);
                }
                if(node.right != null) {
                    queue.offer(node.right);
                }
                size --;
            }
            //扩展次数加1
            ans ++;
        }
        return ans;
    }






}
